package com.jzxk.stu.algorithm;

import org.slf4j.Logger;
import org.slf4j.LoggerFactory;

/**
 * @author 今朝惜客
 * @CreateTime : 16/9/19 下午3:51
 * @Description : 快速排序
 */
public class QuickSort {

	private static final Logger LOG = LoggerFactory.getLogger(QuickSort.class);

	public static void quickSort(Integer[] numbers, int start, int end) {


		if (numbers.length>0){

			_quickSort(numbers,start,end);
		}
	}

	private static void _quickSort(Integer[] numbers, int start, int end){

		if (start<end){

			int middle=getMiddle(numbers, start, end);

			_quickSort(numbers,start,middle-1);
			_quickSort(numbers,middle+1,end);
		}
	}

	/**
	 * 获取中轴
	 * @param numbers
	 * @param low
	 * @param height
	 * @return
	 */
	private static int getMiddle(Integer[] numbers, int low, int height){

		int base=numbers[low];
		int temp;
		while (low<height){

			while (numbers[height]>base&&low<height){
				height--;
			}

			while (numbers[low]<base&&low<height){
				low++;
			}

			if (low<height){

				temp=numbers[height];
				numbers[height]=numbers[low];
				numbers[low]=temp;
			}
		}

		numbers[low]=base;
		return low;
	}
}
